package Tree;

import sun.reflect.generics.tree.Tree;

import java.util.HashSet;
import java.util.Stack;

/**
 *  题目 ：二叉搜索树中两个节点的值之和
 *  题目详述 ：
 *  给定一个二叉搜索树的 根节点 root 和一个整数 k ,
 *  请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。
 */
public class FindTarget {
    /**
     * 核心思想 ：
     *  在二叉搜索树中寻找两个节点，使得两个节点之和为指定值k；
     * 方法一 ：
     *  适用于所有的二叉树（并没有运用到二叉搜索树的特性）
     *  （1）即，在遍历整个二叉树的过程中（迭代/递归），使用哈希表来存储每个遍历到的节点值，
     *  （2）若是在遍历到某个节点时，在哈希表中存在 target（目标节点值之和） - current（当前节点值）的节点的话，
     *  ===》 即，说明target是成立的，即二叉树中存在两个节点值之和 = target节点值；
     */
//    public boolean findTarget(TreeNode root, int k) {
//        HashSet<Integer> set = new HashSet<>();
//        Stack<TreeNode> stack = new Stack<>();
//        TreeNode node = root;
//        while(node != null || !stack.isEmpty()){
//            while(node != null){
//                stack.push(node);
//                node = node.left;
//            }
//            node = stack.pop();
//            Integer value = node.val;
//            // 判断哈希表中是否存在value = target（目标节点值之和） - current（当前节点值）的节点
//            if(set.contains(k - value)){
//                return true;
//            }
//            // 需要将每个所遍历到的节点值加入到哈希表中；
//            set.add(value);
//            node = node.right;
//        }
//        return false;
//    }
    /**
     * 分析 ：
     * 空间复杂度 ：需要O（n）空间大小的哈希表；同时，需要，O（h）的栈空间（h，为二叉树的深度，同时栈用来在遍历二叉树时，存储二叉树的节点）
     * 时间复杂度 ：由于需要去遍历一遍二叉树的节点，即所需要的时间复杂度 O（n）
     */

    /**
     * 方法二 ：双指针
     * （1）使用二叉树的特性，即常规中序遍历的情况下，其所遍历节点值是从小到大进行排序的；
     * （2）即，需要去使用双指针，分别指向二叉搜索树的最左子节点和最右子节点（最左子节点，代表二叉树中的最大值；最右子节点，所代表的是二叉树中的最小值）
     * （3）即，若是双指针所指向的节点值之和大于target，即右指针左移 ；若是双指针所指向的节点值之和小于 target，即左指针右移；
     */
    public boolean findTarget(TreeNode root, int k) {
        // 特殊情况 ：根节点为null，直接返回false即可
        if (root == null){
            return false;
        }
        TreeNode node = new TreeNode();
        node = root;
        Iterator iterator = new Iterator(node);
        ReversedIterator reversedIterator = new ReversedIterator(node);
        int iteratorValue = iterator.next();
        int reversedIterratorValue = reversedIterator.next();
        while(reversedIterratorValue != iteratorValue){
            // 若是双指针所指向的节点值之和 == target的话，直接返回true即可；
            if(iteratorValue + reversedIterratorValue == k){
                return true;
            }
            // 若是双指针所指向的节点值之和 > target的话，使得右指针左移（即，等价于减少右指针所指向节点的值）
            else if (iteratorValue + reversedIterratorValue > k) {
                reversedIterratorValue = reversedIterator.next();
            }
            // 若是双指针所指向的节点值之和 < target的话，使得左指针右移（即，等价于增加左指针所指向节点的值）
            else if (iteratorValue + reversedIterratorValue < k){
                iteratorValue = iterator.next();
            }
        }
        return false;
    }

    // 常规中序遍历迭代器
    // 中序遍历顺序 ： 左子树 - 根节点 - 右子树
    // 特点 ：(获取二叉搜索树中的节点是从小到大，即获取到的第一个节点为二叉搜索树中最左子节点)
    public class Iterator{
        TreeNode node;
        Stack<TreeNode> stack;
        public Iterator(TreeNode root){
            node = root;
            stack = new Stack<TreeNode>();
        }

        public boolean hasnext(){
            return node != null || !stack.isEmpty();
        }

        public int next(){
            while(node != null){
                stack.push(node);
                node = node.left;
            }

            node = stack.pop();
            Integer value = node.val;
            node = node.right;
            return value;
        }
    }

    // 反转中序遍历迭代器
    // 中序遍历顺序 ： 右子树 - 根节点 - 左子树
    // 特点 ：(获取二叉搜索树中的节点是从大到小，即获取到的第一个节点为二叉搜索树中最右子节点)
    public class ReversedIterator{
        TreeNode node;
        Stack<TreeNode> stack;
        public ReversedIterator(TreeNode root){
            node = root;
            stack = new Stack<TreeNode>();
        }

        public boolean hasnext(){
            return node != null || !stack.isEmpty();
        }

        public int next(){
            while(node != null){
                stack.push(node);
                node = node.right;
            }

            node = stack.pop();
            Integer value = node.val;
            node = node.left;
            return value;
        }
    }
    /**
     * 分析来说 ：
     * （1）时间复杂度 ：由于使用双指针的话，还是需要去遍历整个二叉树，所以时间复杂度为 O（n）；
     * （2）空间复杂度 ：由于使用中序遍历迭代器和反转中序遍历迭代器，会各自使用到 O（h）的栈 [h,所指向的是二叉树的深度]；
     * 结论 ：总的来说，双指针算法的空间复杂度，可能远远小于哈希表算法；
     */
}
